class Node(object):
    def __init__(self, data=None):
        self.data = data
        self._next = None
        self._prev = None


class List(object):
    def __init__(self):
        self.head = Node()
        self.tail = Node()

        # intialize the head and tail vars.
        self.head.next = self.tail
        self.tail.prev = self.head

        self.length = 0
        self.index = 0

    def insert(self, pos, data):
        assert pos >= 0 and pos <= self.length

        # Find out the position to insert.
        tmpPtr = self.head
        while pos > 0:
            tmpPtr = tmpPtr.next
            pos -= 1

        # Insert new node
        newNode = Node()
        newNode.data = data

        curNode = tmpPtr
        nextNode = tmpPtr.next

        curNode.next = newNode
        newNode.prev = curNode

        newNode.next = nextNode
        if nextNode:
            nextNode.prev = newNode

        self.length += 1

    def __len__(self):
        return self.length

    def append(self, data):
        self.insert(self.length, data)

    def remove(self, pos):
        assert pos < self.length and pos >= 0

        tmpPtr = self.head.next
        while pos > 0:
            tmpPtr = tmpPtr.next
            pos -= 1

        prevNode = tmpPtr.prev
        nextNode = tmpPtr.next

        prevNode.next = nextNode
        if nextNode:
            nextNode.prev = prevNode

        self.length -= 1

    def __iter__(self):
        tmpPtr = self.head.next
        while tmpPtr != self.tail:
            yield tmpPtr.data
            tmpPtr = tmpPtr.next

    def __next__(self):
        if self.index >= self.length:
            self.index = 0
            raise StopIteration()

        item = self[self.index]
        self.index += 1
        return item

    def foreach(self, flag=True):
        if flag:
            tmpPtr = self.head.next
            while tmpPtr != self.tail:
                yield tmpPtr.data
                tmpPtr = tmpPtr.next
        else:
            tmpPtr = self.tail.prev
            while tmpPtr != self.head:
                yield tmpPtr.data
                tmpPtr = tmpPtr.prev

    def __setitem__(self, key, val):
        print("__setitem__ called")
        assert isinstance(key, int)
        self.insert(key, val)

    def __delitem__(self, key):
        print("__delitem__ called")
        assert isinstance(key, int)
        self.remove(key)

    def __getitem__(self, key):
        print("__getitem__ called")
        assert isinstance(key, int)
        assert key >= 0 and key < self.length

        tmpPtr = self.head.next
        while key > 0:
            tmpPtr = tmpPtr.next
            key -= 1

        return tmpPtr.data

    def clean(self):
        while len(self):
            self.remove(0)


def print_iter(x):
    for l in x:
        print(l)


if __name__ == "__main__":
    l = List()
    l.append(1)
    l.append(2)
    l.append(3)

    print_iter(l)
    l[1] = 4
    del l[1]
